package binarySearch;

public class mySqrt {
    public int mySqrt(int x) {
        long left=0;
        long right=x;
        if(x<1) return 0;
        while(left<=right){
            long mid=left+(right-left+1)/2;
            if(mid*mid<x) left=mid+1;
            else if(mid*mid>x) right=mid-1;
            else return (int)mid;
        }
        if(left*left>x) return (int)left-1;
        else return (int)left;
    }
}
